package leetcode.editor.cn;

import java.util.Arrays;

/**
 * [268]丢失的数字
 * missing-number
 */
//给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
// 示例 1：
//输入：nums = [3,0,1]
//输出：2
//解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。 
//
// 示例 2：
//输入：nums = [0,1]
//输出：2
//解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。 
//
// 示例 3：
//输入：nums = [9,6,4,2,3,5,7,0,1]
//输出：8
//解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。 
//
// 示例 4：
//输入：nums = [0]
//输出：1
//解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。 
//
// 提示：
// n == nums.length 
// 1 <= n <= 104 
// 0 <= nums[i] <= n 
// nums 中的所有数字都 独一无二
//
// 进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题? 
// Related Topics 位运算 数组 哈希表 数学 排序 
// 👍 498 👎 0

public class LC268_丢失的数字 {
    public static void main(String[] args) {
        Solution solution = new LC268_丢失的数字().new Solution();
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        int result = solution.missingNumber(nums);
        System.out.println("result = " + result);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int missingNumber(int[] nums) {
            /*
               系统排序法：直接对 nums进行排序，找到符合 nums[i] !=i 的位置即是答案，否则 n 为答案。
               int n = nums.length;
               Arrays.sort(nums);
               for (int i = 0; i < nums.length; i++) {
                   if (nums[i] != i){
                       return i;
                   }
               }
               return n;*/
            /*
                数组哈希：利用 nums的数值范围为[0,n]，且只有一个值缺失，
                我们可以直接开一个大小为 n + 1的数组充当哈希表，
                进行计数，没被统计到的数值即是答案。
            int n = nums.length;
            boolean[] hash = new boolean[n + 1];
            for (int i = 0; i < n; i++) {
                hash[nums[i]] = true;
            }
            for (int i = 0; i < n; i++){
                if (!hash[i]){
                    return i;
                }
            }
            return n;*/
            /*
            利用nums的数值范围为[1,n]，我们可以先计算出[1,n]的总和sum（利用等差数列求和公式），
            再计算nums的总和target，两者之间的差值即是nums中缺失的数字。

            int n = nums.length;
            //计算不缺失情况下的总和
            int sum = (1 + n) * n / 2;
            int target = 0;
            //计算源数组和
            for (int num : nums) {
                target += num;
            }
            return sum - target;*/
            /*
            异或
            我们可以先求得 [1, n]的异或和ans，然后用ans对各个nums[i]进行异或。
            这样最终得到的异或和表达式中，只有缺失元素出现次数为1次,
            其余元素均出现两次（x⊕x=0），即最终答案 ans为缺失元素。
             */
            int n = nums.length;
            int ans = 0;
            //对整个数组异或
            for (int num : nums) {
                ans = ans ^ num;
            }
            //将以上异或和与不缺失情况下的数组异或，必然得到一个落单的数，注意两个相同的数异或==0
            for (int i = 0; i <= n; i++) {
                ans = ans ^ i;
            }
            return ans;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}